/**
 * 
 */
package calculation;

import java.util.List;
import java.util.ArrayList;

/**
 * @author Michael
	The gray code is a binary numeral system where two successive values differ in only one bit.
	
	Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
	
	For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
	00 - 0
	01 - 1
	11 - 3
	10 - 2
	
	Each bit is inverted if the next higher bit of the input value is set to one. 
	
	
	http://www.mitbbs.com/article_t/JobHunting/32128561.html
 */
public class GrayCode {

	
	public static List<Integer> grayCode(int n) {
		assert (n > 0);
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0, size = 1 << n; i < size; ++i) {
			list.add(i ^ (i >> 1));
		}
		return list;
	}
	
	
	
	/*
    The purpose of this function is to convert an unsigned
    binary number to reflected binary Gray code.
	*/
//	unsigned int binaryToGray(unsigned int num)
//	{
//	    return (num >> 1) ^ num;
//	}

	/*
	    The purpose of this function is to convert a reflected binary
	    Gray code number to a binary number.
	*/
//	unsigned int grayToBinary(unsigned int num)
//	{
//		unsigned int numBits = 8 * sizeof(num);
//		unsigned int shift;
//		for (shift = 1; shift < numBits; shift *= 2)
//		{
//		    num ^= num >> shift;
//		}
//		return num;
//	}
	
	/**
	 * 
	 */
	public GrayCode() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 3;
		List<Integer> list = grayCode(n);
		for (int i : list) {
			System.out.println(i);
		}
		
		
	}

}
